
using System;
using System.Threading;
using System.IO;
using System.Collections;
 
	
	public class Node{
		string name;
		ArrayList children = new ArrayList(); // List of string (atom) or Node children
		public Node (string name)
		{
			this.name = name;
		}
		public void add(Object child){
			children.Add(child);
		}
		public string Name {
			get {
				return this.name;
			}
		}
	    public Node childNode(int index){
		  return (Node)Children[index];
	    }

		public ArrayList Children {
			get {
				return this.children;
			}
		}
	
		public static string nodeString(Object nodeOrAtom){
			StringWriter sw = new StringWriter();
			NodeWriter wrt = new NodeWriter(sw);
			wrt.write(nodeOrAtom);
			return sw.ToString();
 		}


	    public static bool eq(Object o1, Object o2){
		  if( o1 is string ){
			return ((string)o1).Equals(o2);
		  }else if( !(o2 is Node) ){
			return false;
		  }else{
			var n1 = (Node)o1;
			var n2 = (Node)o2;
			if( ! n1.name.Equals(n2.name) ){
			  return false;
			}
			if( n1.Children.Count != n2.children.Count ){
				return false;
			}
			for( int i=0; i<n1.Children.Count; i++ ){
				if( ! eq(n1.Children[i], n2.children[i]) ){
					return false;
				}
			}
			return true;
		  }
	    }
	}
	
	class NodeWriter{
		TextWriter w;
		
		public NodeWriter (TextWriter w)
		{
			this.w = w;
		}


  	    public void writeln(Object nodeOrAtom){
		  write(nodeOrAtom);
		  w.WriteLine();
	    }

		public void write(Object nodeOrAtom){
			if( nodeOrAtom is Node ){
				write( (Node)nodeOrAtom );
			}else{
				w.Write(nodeOrAtom);
			}
		}
		public void write(Node n){
			w.Write ("("+n.Name);
			foreach(Object c in n.Children){
				w.Write(" ");
				write(c);
			}
			w.Write (")");
		}
	}

public class Parser
{


    public Object parse(string text){
		int idx=0;
		return parse (text, ref idx);
	}

	 Object parse(string text, ref int i){
		skipSpace(text, ref i);
		if( text[i]=='(' ){
			return parseGroup(text, ref i);
		}else{
			string atom = parseAtom(text, ref i);
			//Console.WriteLine("atom "+atom);
			return atom;
		}
	}
	
	 void skipSpace(string text, ref int pos){
		while(pos < text.Length && spaceChar(text[pos])){
			pos++;
		}
		if( pos<text.Length && text[pos]=='#' ){
			// skip single line comment
			while(pos < text.Length && text[pos]!='\n'){
				pos++;
			}
			skipSpace(text, ref pos); // there can be space after comment too
		}
	}

	 Object parseGroup(string text, ref int idx){
		if( text[idx]!='(' ){
			throw new Exception("not ( char at "+idx+" in "+text);
		}
		idx++;
		//Console.WriteLine("group start");
		string groupName = (string)parse(text, ref idx);
		Node res = new Node(groupName);
		for(;;){
			//Console.WriteLine("group remaining "+text.Substring(idx));
			skipSpace(text, ref idx);
			if( text[idx]==')' ){
				idx++;
				break;
			}
			Object o = parse (text, ref idx);
			res.add(o);
		}
		//Console.WriteLine("group end");
		return res;
	}

	 string parseAtom(string text, ref int idx){
		if( !atomChar(text[idx]) ){
			throw new Exception("non-atom char at "+idx+" in "+text);
		}
		int end=idx;
		for( int i=idx; i<text.Length; i++ ){
			if( !atomChar(text[i]) ){
				end=i;
				break;
			}
		}
		string ret = text.Substring(idx, end-idx);
		idx = end;
		return ret;
	}
	
			
	 bool spaceChar(char c){
			return c==' ' || c=='\t' || c=='\n';
	}
	
	 bool atomChar(char c){
		return !spaceChar(c) && c!='(' && c!=')';
	}
	
 
}
